package com.wyw.learning.offer;

/**
 * 在排序数组中查找出现的次数
 *
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/17 13:42
 */
public class Offer053 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,8,8,8,8,8,9};
        System.out.println(search(nums, 8));

//        int[] nums1 = new int[]{0,1,2,3,5,6,7,8};
        int[] nums1 = new int[]{0};
        System.out.println(missingNumber(nums1));
    }

    // 最简单的一次循环查找
//    public static int search(int[] nums, int target) {
//        int result = 0;
//        for (int num : nums) {
//            if(num == target)
//                result ++;
//            if(num > target)
//                return result;
//        }
//        return result;
//    }

    // 官方想问的
    public static int search(int[] nums, int target) {
        int left =0,right = nums.length-1;
        int count = 0;
        while(left<right){
            int mid = (left+right)/2;
            if(nums[mid]>=target)
                right=mid;
            if(nums[mid]<target)
                left = mid+1;
        }
        while(left<nums.length&&nums[left++]==target)
            count++;
        return count;
    }

    // 简单实现
//    public static int missingNumber(int[] nums) {
//        int length = nums.length;
//        for(int i = 0; i < length; i++) {
//
//            if(nums[i] != i)
//                return i;
//        }
//        return nums[length-1] +1;
//    }

    // 数学方法
//    public static int missingNumber(int[] nums) {
//        //计算出0-n的和  n*(n+1)/2
//        int sum = nums.length * (nums.length+1)/2;
//        return  sum - Arrays.stream(nums).sum() ;
//    }

    // 二分法
    public static int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
